package dp.bag_problem;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-09-02 21:11
 */
public class is_0_1_bag_one_dimensional {
    // dp定义：dp[j] 表示容量为j的背包，能放入物品的最大价值
    // 递推式：dp[i][j] = max(dp[j] , dp[j - weight[i]] + value[i])  不选第i个物品 or 选第i个物品，取两者较大值
    // 初始化：dp[0] = 0
    // 返回值: dp[bagSize]

    @Test
    public void test() {
        System.out.println(weightBag01bag(new int[]{15, 20, 30}, new int[]{1, 3, 4}, 4));
    }


    // 如果采用正序遍历j，当遍历第一个物品的时候
    // dp[1] = dp[1 - weight[0]] + value[0] = 15
    // dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 15 + 15 = 30 (显然重复计算了一次)

    // 采用逆序遍历j，当遍历第一个物品的时候
    // dp[2] = dp[2 - weight[0]] + value[0] = 0 + 15 = 15
    // dp[1] = dp[1 - weight[0]] + value[0] = 15
    /**
     * 注意，传入的value和weight数组的元素都应该是升序的
     *
     * @param value   各背包的价值
     * @param weight  各背包的重量
     * @param bagSize 背包容量
     */
    public int weightBag01bag(int[] value, int[] weight, int bagSize) {
        int[] dp = new int[bagSize + 1];
        for (int i = 0; i < weight.length; i++) { // 先遍历物品
            for (int j = bagSize; j >= weight[i]; j--) { // 再遍历背包
                // 倒序遍历，是防止某一个物品被重复添加
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }

            // 打印 dp数组
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[j] + " ");
            }
            System.out.println();
        }
        return dp[bagSize];
    }
}
